package algorithm.t202111;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/9 9:10
 * @description :3道
 * 无言，努力。
 * persevere to last
 * 2021.11.09
 * 2021年11月9日19:43:40
 * 李红磊
 */
public class t20211109 {
    //488.祖玛游戏
    private int[] hand = new int[26];
    private char[] colors = {'R', 'Y', 'B', 'G', 'W'};
    private int res = Integer.MAX_VALUE;

    public int findMinStep(String board, String hand) {
        if (hand.length() == 1 && board.length() == 1) {
            return -1;
        }
        for (int i = 0; i < hand.length(); i++) {
            this.hand[hand.charAt(i) - 'A']++;
        }

        dfs(new StringBuffer(board), 0);

        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /*
       大致分两种情况深度优先搜索：
           （1）插入一个或两个颜色相同的球引发连锁反响。
           （2）往两个颜色相同的球中间插入一个颜色不同的球（为什么要这么做呢？见特殊测试用例）。

           "RRYGGYYR-RYGGYYRR"
           "GGBBB"
            需要先在中间插入一个B，5
       */
    private void dfs(StringBuffer curBoard, int step) {
// 剪枝，如果当前step已经大于等于全局的result，则没必要继续深入了
        if (step >= res) {
            return;
        }
        // 如果消除完则更新全局result
        if (curBoard.length() == 0) {
            res = Math.min(step, res);
            return;
        }

        //遍历dfs求解
        for (int i = 0; i < curBoard.length(); i++) {
            char ball = curBoard.charAt(i);
            int j = i;
            if (j + 1 < curBoard.length() && ball == curBoard.charAt(j + 1)) j++;

            //只有单个球的时候我们视图插入两个颜色相同的球
            //如桌子上有WRRB 我们手中有WWR，那么我们就插入WW
            if (i == j && hand[ball - 'A'] >= 2) {
                StringBuffer temp = new StringBuffer(curBoard);
                temp.insert(i, ball + "" + ball);
                hand[ball - 'A'] -= 2;
                dfs(eliminate(temp), step + 2);
                hand[ball - 'A'] += 2;
            } else if (j == i + 1) {
                //说明两个球颜色相同并且相邻
                //如：WWRBG

                //我们视图在这两个（WW)前面插入一个颜色相同的（W）球
                //先判断我们有没有W球
                if (hand[ball - 'A'] >= 1) {
                    //若我们有至少一个W球，我们就将其放在WW前面
                    StringBuffer temp = new StringBuffer(curBoard);
                    temp.insert(i, ball);
                    hand[ball - 'A']--;
                    dfs(eliminate(temp), step + 1);
                    hand[ball - 'A']++;

                }

                //往这两个颜色相同且相邻的球中间插入一个颜色不同的球
                for (char color : colors) {
                    if (color != ball && hand[color - 'A'] >= 1) {
                        StringBuffer temp = new StringBuffer(curBoard);
                        temp.insert(i + 1, color);
                        hand[color - 'A']--;
                        dfs(temp, step + 1);
                        hand[color - 'A']++;
                    }

                }


            }


        }

    }

    private StringBuffer eliminate(StringBuffer temp) {
        boolean flag = true;
        while (flag) {
            flag = false;

            for (int i = 0; i < temp.length(); i++) {
                int j = i + 1;
                while (j < temp.length() && temp.charAt(i) == temp.charAt(j)) {
                    j++;
                }

                if (j - i >= 3) {
                    temp.delete(i, j);
                    flag = true;
                    break;//删除，跳出本次循环，继续删除
                }

            }

        }
        return temp;
    }


    //1143.最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.equals(text2)) return text1.length();

        int res = 0;
        int t1_len = text1.length(), t2_len = text2.length();

        for (int i = 0; i < t1_len; i++) {
            for (int j = 0; j < t2_len; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    int count = 1;
                    int p1 = i + 1, p2 = j + 1;
                    while (p1 < t1_len && p2 < t2_len) {
                        if (text1.charAt(p1) == text2.charAt(p2)) {
                            count++;
                            p1++;
                            p2++;
                        } else {
                            p1++;
                        }

                    }
                    res = Math.max(res, count);
                }

            }


        }

        return res;
    }

    public int longestCommonSubsequence2(String text1, String text2) {
        /*
        求两个数组或者字符串的最长公共子序列问题，肯定是要用动态规划的
        首先，区分两个概念：子序列可以是【不连续的】；子数组（子字符串）需要是【连续的】；
        另外，动态规划也是有套路的：单个数组或者字符串要用动态规划时，
        可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，
        可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

         */
        if (text1.equals(text2)) return text1.length();
        int len1 = text1.length(), len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

            }
        }

        return dp[len1][len2];
    }


    //583.两个字符串的删除操作
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();

        int[][] dp = new int[len1 + 1][len2 + 1];

        //定义 f[i][j]f[i][j] 代表考虑 s1s1 的前 ii 个字符、考虑 s2s2 的前 jj 个字符（最终字符串不一定包含 s1[i]s1[i] 或 s2[j]s2[j]）时形成相同字符串的最小删除次数。

        for (int i = 0; i <= len1; i++) dp[i][0] = i;
        for (int i = 0; i <= len2; i++) dp[0][i] = i;

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);
                }
            }
        }

        return dp[len1][len2];
    }


    public static void main(String[] args) {
        t20211109 t20211109 = new t20211109();
        System.out.println(t20211109.longestCommonSubsequence2("abcde", "ace"));

    }

}


